package my.algo;

/**
 * 一个整数与自己异或的结果是0，一个整数与0异或的结果是自己，所以 a ^ b ^ b = a
 * 异或操作满足交换律，即a^b=b^a。
 */
public class 异或 {

    public static void basic() {
        // 0^a == a
        int i = 0;
        System.out.println(i ^ 9);

        // a^b^b == a
        int a = 5;
        int b = a ^ 8;
        int c = b ^ 8;
        System.out.println(c);
    }

    /**
     * 数组中有一些数，其中一个是奇数个，其它是偶数个，找出是奇数个的那个数
     */
    public static void printOddTimesNum(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        System.out.println(eor);
    }

    /**
     * 数组中有一些数，其中两个是奇数个，其它是偶数个，找出是奇数个的那两个数
     */
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        // eor == a ^ b a和b为奇数个
        // a != b，所以eor != 0，所以eor对应的二进制上必然有一个位置上是1
        // 提取出最小位的1
        // eor ==      1 0 1 0 1 1 1 0 0
        // ~eor ==     0 1 0 1 0 0 0 1 1
        // ~eor + 1 == 0 1 0 1 0 0 1 0 0
        // rightOne == 0 0 0 0 0 0 1 0 0
        int rightOne = eor & (~eor + 1);

        int res1 = 0;
        for (int i : arr) {
            // 最小位上等于0的进行异或
            if ((i & rightOne) == 0) {
                res1 ^= i;
            }
        }
        System.out.println("res1 = " + res1 + " res2=" + (eor ^ res1));
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 4, 4, 5, 5};
        printOddTimesNum2(arr);
    }
}
